<!DOCTYPE html>
<html lang="zh">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<meta http-equiv="X-UA-Compatible" content="ie=edge">
	<title>Document</title>
</head>
<body>
	<script>
		let array = [10,9,8,7,6,5,4,3,2,1,0];
		
		function bubbleSort(arr){
			let length = arr.length;
			for(let i=0; i<length; i++){ //外循环会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序
				//从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较
				for(let j=0; j<length-1-i; j++){ //内循环将从第一位迭代至倒数第二位，内循环实际上进行当前项和下一项的比较
					if(arr[j] > arr[j+1]){
						[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
					}
				}
			}
		}
	
	
		/**
		 * 快速排序 
		 * 1、首先，从数组中选择中间一项作为主元
		 * 2、创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。
		 * 移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。
		 * 这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分操作
		 * 3、接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序
		 * 
		**/
		array = [3,4,7,6,1,2,0,9,8,5,10];
		
		function quickSort(){
			quick(array, 0, array.length-1);  //开始声明一个主方法来调用递归函数，传递待排序数组，以及索引0及其最末的位置（因为我们要排整个数组，而不是一个子数组）作为参数
		}
		function quick(arr, left, right){
			let index;  //该变量将子数组分离为较小值数组和较大值数组
			//如果数组的长度比1大（因为只有一个元素的数组必然是已排序了的，对给定子数组执行partition操作
			if(arr.length > 1){
				index = partition(arr, left, right); //第一次调用是针对整个数组
			
				if(left < index - 1){ //如果子数组存在较小值的元素
					quick(arr, left, index-1);
				}
				if(index < right){
					quick(arr, index, right);
				}
			}
		}
		//划分过程
		function partition(arr, left, right){
			let pivot = arr[Math.floor((right+left)/2)], //基准数
					l = left,
					r = right;
			while(l<r){
				while(arr[l]<pivot){
					l++;
				}
				while(arr[r]>pivot){
					r--;
				}
				if(l<=r){
					[arr[l], arr[r]] = [arr[r], arr[l]]; //当左边大于或等于，右边小于或等于就交换
					l++;
					r--;
				}
			}
			return l;
		}
		
		/**  [3,4,7,6,1,2,0,9,8,5,10]  //基准数为2
		  *  左指针指到3，右指针指到0，交换
			*  [0,4,7,6,1,2,3,9,8,5,10]
			*  左指针指到4，右指针指到2，交换
			*  [0,2,7,6,1,4,3,9,8,5,10]
			*  左指针指到7，右指针指到1，交换
			*  [0,2,1,6,7,4,3,9,8,5,10]
			*  最终左指针为3
			*  然后[0,2,1]为一组，[6,7,4,3,9,8,5,10]为一组
			* =========================
			* [0,2,1] //基准数为2
			* 左指针指到2，右指针指到1，交换
			* [0,1,2]
			* 
			* =========================
			* [6,7,4,3,9,8,5,10]  //基准数为
			* 
			* 
			* 
			* 
		 **/
		
	</script>
</body>
</html>